package algorithm;

/**
 * @Author wangtengyu
 * @Create 2018-03-22-13:54
 * 插入排序 其实插入的是自身
 */
public class InsertSort {

    public static int[] sort(int[] array){
        //默认array[0]不排序
        for(int i=1;i<array.length;i++){
            //要插入的数据
            int temp=array[i];
            int j=i;//定义一个j是为了进行后面的增减运算
            while(j>0&&temp<array[j-1]){// j>0保证的是后面比较的最后元素是array[0]； while是并不是每一次循环都有
                array[j]=array[j-1];
                j--;
            }
            array[j]=temp;
        }
        return array;
    }


    //遍历显示数组
    public static void display(int[] array){
        for(int i = 0 ; i < array.length ; i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args){
        int[] array = {4,2,8,9,5,7,6,1,3};
        //未排序数组顺序为
        System.out.println("未排序数组顺序为：");
        display(array);
        System.out.println("-----------------------");
        array = sort(array);
        System.out.println("-----------------------");
        System.out.println("经过插入排序后的数组顺序为：");
        display(array);
    }
}
